package main.Q1701_1800;

public class Q1711_1720 {
    public static void main(String[] args) {
        System.out.println("Question1711：");
        System.out.println("Question1712：将数组分成三个子数组的方案数");
        System.out.println("Question1713：");
        System.out.println("Question1714：");
        System.out.println("Question1715：");
        System.out.println("Question1716：");
        System.out.println("Question1717：");
        System.out.println("Question1718：");
        System.out.println("Question1719：");
        System.out.println("Question1720：解码异或后的数组");
    }
}

class Question1712 {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int[] sums = new int[n];// 计算前缀和
        sums[0] = nums[0];
        for (int i = 1; i < n; i++) sums[i] = sums[i - 1] + nums[i];
        final int MOD = 1000000000 + 7;
        long ans = 0;
        int t = sums[n - 1] / 3;
        for (int i = 0; i < n && sums[i] <= t; i++) {
            int left = lowerBound(i + 1, n - 1, sums, sums[i] * 2);
            int right = upperBound(i + 1, n - 1, sums, sums[i] + (sums[n - 1] - sums[i]) / 2);
            if (right >= left) {
                ans += right - left + 1;
            }
        }
        return (int) (ans % MOD);
    }

    public int lowerBound(int left, int right, int[] nums, int target) {
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    public int upperBound(int left, int right, int[] nums, int target) {
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left - 1;
    }
}

class Question1720 {
    public int[] decode(int[] encoded, int first) {
        int[] result = new int[encoded.length + 1];
        result[0] = first;
        for (int i = 1; i < result.length; i++) {
            result[i] = encoded[i - 1] ^ result[i - 1];
        }
        return result;
    }
}